#include "stdafx.h"
#include "CMergeSort.h"
#include "include/tool.h"
#include <gtest/gtest.h>


template <typename T>
void _merge_sort_merge(std::vector<T> *A, int p, int q, int r) {
    int n1 = q-p+1;
    std::vector<T> L;
    for (int i = 0; i < n1; ++i) {
        L.push_back(A->at(p+i));
    }
    L.push_back(std::numeric_limits<T>::max());

    int n2 = r-q;
    std::vector<T> R;
    for (int i = 0; i < n2; ++i) {
        R.push_back(A->at(q+i+1));
    }
    R.push_back(std::numeric_limits<T>::max());

    int i = 0, j = 0;
    for (int k = p; k < r+1; ++k) {
        if (L[i] < R[j]) {
            (*A)[k] = L[i++];
        } else {
            (*A)[k] = R[j++];
        }
    }
}

template <typename T>
void _merge_sort_merge_test_empty(std::vector<T> *A, int p, int q, int r) {
    int n1 = q-p+1;
    std::vector<T> L;
    for (int ii = 0; ii < n1; ++ii) {
        L.push_back(A->at(p+ii));
    }

    int n2 = r-q;
    std::vector<T> R;
    for (int ii = 0; ii < n2; ++ii) {
        R.push_back(A->at(q+ii+1));
    }

    int i = 0, j = 0;
    for (int k = p; k < r+1; ++k) {
        if (i >= n1) {
            for (int l = k; l < r+1; ++l) {
                (*A)[k] = R[j+l-k];
            }
            return;
        }

        if (j >= n2) {
            for (int l = k; l < r+1; ++l) {
                (*A)[k] = L[i+l-k];
            }
            return;
        }

        if (L[i] < R[j]) {
            (*A)[k] = L[i++];
        } else {
            (*A)[k] = R[j++];
        }
    }
}

template <typename T>
int _merge_sort_reverse_number(std::vector<T> *A, int p, int q, int r) {
    int n1 = q-p+1;
    std::vector<T> L;
    for (int ii = 0; ii < n1; ++ii) {
        L.push_back(A->at(p+ii));
    }
    L.push_back(std::numeric_limits<T>::max());

    int n2 = r-q;
    std::vector<T> R;
    for (int ii = 0; ii < n2; ++ii) {
        R.push_back(A->at(q+ii+1));
    }
    R.push_back(std::numeric_limits<T>::max());

    int cn = 0;
    int i = 0, j = 0;
    for (int k = p; k < r+1; ++k) {
        if (L[i] <= R[j]) {
            (*A)[k] = L[i++];
        } else {
            cn += n1 - i;
            (*A)[k] = R[j++];
        }
    }
    return cn;
}

template <typename T>
void merge_sort(std::vector<T> *A, int p, int r) {
    if (p < r) {
        int q = std::floor((double)(p + r)/2);
        merge_sort(A, p, q);
        merge_sort(A, q+1, r);
        //_merge_sort_merge(A, p, q, r);
        _merge_sort_merge_test_empty(A, p, q, r);
    }
}

template <typename T>
void merge_sort_reverse_number(std::vector<T> *A, int *cnt, int p, int r) {
    if (p < r) {
        int cn = 0;
        int q = std::floor((double)(p + r)/2);
        merge_sort_reverse_number(A, cnt, p, q);
        merge_sort_reverse_number(A, cnt, q+1, r);
        *cnt += _merge_sort_reverse_number(A, p, q, r);
    }
}

CMergeSort::CMergeSort()
{
    //ctor
}

CMergeSort::~CMergeSort()
{
    //dtor
}

int CMergeSort::run(void) {
    int A[] = {31, 41, 59, 26, 41, 58, 33, 78};

    std::cout << "merge sort :";
    std::vector<int> mergeVector = create_from_array(A, SIZE(A));
    print_vector(mergeVector);
    merge_sort(&mergeVector, 0, mergeVector.size()-1);
    print_vector(mergeVector);

    std::cout << "merge sort and calc reverse number :";
    int cnt = 0;
    std::vector<int> tmp1 = create_from_array(A, SIZE(A));
    print_vector(tmp1);
    merge_sort_reverse_number(&tmp1, &cnt, 0, tmp1.size()-1);
    std::cout << "the reverse number :" << cnt << std::endl;
    print_vector(tmp1);
    return 0;
}

TEST(CMergeSort, run)
{
	CMergeSort().run();
}